package 分类.一维动规;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class 俄罗斯套娃信封问题 {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]){
                    return o2[1]-o1[1];
                }else {
                    return o1[0]-o2[0];
                }
            }
        });
        int[] nums=new int[envelopes.length];
        for (int i=0;i<envelopes.length;i++) {
            nums[i]=(envelopes[i][1]);
        }

        return lengthOfLIS(nums);
    }

    int lengthOfLIS(int[] nums){
        int[] dp=new int[nums.length];
        Arrays.fill(dp,1);
        for (int i=0;i<nums.length;i++){
            for (int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res=0;
        for (int i : dp) {
            res=Math.max(res,i);
        }
        return res;
    }
}
